package editortrees;

import java.util.Stack;

import editortrees.Node.Code;

// A height-balanced binary tree with rank that could be the basis for a text editor.

/**
 * An edit tree can have nodes that are inserted and deleted at a given position in the tree.
 * 
 * @author riechelp. Created Oct 17, 2012.
 */
public class EditTree {

	private Node root;

	private int rotationCount = 0;

	// this is to avoid recursing the whole tree every time we need this
	// information
	// e.g. boundary checks in many methods
	private int size = 0;

	/**
	 * Debugging purposes only.
	 * 
	 * @param args
	 */
	public static void main(String[] args) {
//		EditTree t1 = new EditTree("ab");
//		// t1.delete(2);
//		t1.add('h'); // so t1.toString() is "abdefhg"
//
//		EditTree t2 = new EditTree("arst");
//		t2.add('B');
//		t2.add('A', 0);
//		t2.add('D');
//		t2.add('C', 2);
////		EditTree t1 = makeFullTreeWithHeight(2, 'a');
////		EditTree t2 = makeFullTreeWithHeight(3, 'A');
//		t1.concatenate(t2);
//		DisplayableBinaryTree d = new DisplayableBinaryTree(t1, 1000, 500);
//
//		d.display();
//		// d2.display();

	}

	/**
	 * Display for debug purposes
	 * 
	 */
	public void display() {
		DisplayableBinaryTree d = new DisplayableBinaryTree(this, 1000, 500);
		d.display();
	}

	/**
	 * Construct an empty tree
	 */
	public EditTree() {
		this.root = null;
	}

	/**
	 * Construct a single-node tree whose element is c
	 * 
	 * @param c
	 */
	public EditTree(char c) {
		this.root = new Node(c, null, null, 0, Code.SAME);
		this.size++;
	}

	/**
	 * Make this tree be a copy of e, with all new nodes, but the same shape and contents.
	 * 
	 * @param e
	 */
	public EditTree(EditTree e) {
		this();
		if (e.root == null)
			return;
		this.root = e.root.Copy();
		this.size = e.size;
	}

	/**
	 * Create an EditTree whose toString is s. This can be done in O(N) time, where N is the length of the tree
	 * (repeatedly calling insert() will be N log N).
	 * 
	 * @param s
	 */
	public EditTree(String s) {
		if (s.length() == 0) {
			this.root = null;
			return;
		}
		// A balance code is to the left iff the size is a perfect log_2
		// otherwise it should be same
		// The balance calculation checks to see if the log_2 - the truncated
		// log_2 gives a value within the tolerance, meaning it is a perfect log
		Code balance = (Math.log10(s.length()) / Math.log10(2)
				- (double) ((int) (Math.log10(s.length()) / Math.log10(2) + 0.0001)) < 0.0001)
				&& (int) (Math.log(s.length()) / Math.log10(2)) != 0 ? Code.LEFT : Code.SAME;
		this.root = new Node(s.charAt(s.length() / 2), Node.CreateNode(s.substring(0, s.length() / 2)),
				Node.CreateNode(s.substring(s.length() / 2 + 1, s.length())), s.length() / 2, balance);
		this.size = s.length();
	}

	/**
	 * Added for displaying purposes only
	 * 
	 * @param args
	 */
	public void countInOrder() {
		if (this.root != null) {
			this.root.countInOrder(0, 0);
		}
	}

	/**
	 * 
	 * @return the height of this tree
	 */
	public int height() {
		if (this.root != null)
			return this.root.height() - 1;
		return -1;
	}

	/**
	 * 
	 * @return the number of nodes in this tree
	 */
	public int size() {
		return this.size;
	}

	/**
	 * 
	 * returns the total number of rotations done in this tree since it was created. A double rotation counts as two.
	 * 
	 * @return number of rotations since tree was created.
	 */
	public int totalRotationCount() {
		return rotationCount;
	}

	/**
	 * return the string produced by an inorder traversal of this tree
	 * 
	 * @return the string
	 */
	public String toString() {
		InOrder itr = new InOrder(this);
		StringBuilder s = new StringBuilder();
		for (itr.first(); itr.isValid(); itr.advance()) {
			s.append(itr.current.element);
		}
		return s.toString();
	}

	/**
	 * 
	 * @param c
	 *            character to add to the end of this tree.
	 */
	public void add(char c) {
		this.size++;

		if (this.root == null) {
			this.root = new Node(c, null, null, 0, Code.SAME);
			return;
		}

		Stack<Node> s = new Stack<Node>();
		s.add(this.root);
		// the stack always has at least 1 node (the root)

		Node rightmostNode = this.root;
		while (rightmostNode.right != null) {
			rightmostNode = rightmostNode.right;
			s.add(rightmostNode);
		}
		rightmostNode.right = new Node(c, null, null, 0, Code.SAME);

		// balance after insertion
		while (s.size() > 0) {
			Node parent = s.pop();
			if (parent.balance == Code.RIGHT) {
				if (s.size() > 0) {
					// rotate and attach the rotated subtree to the grandparent
					s.pop().right = singleRotateLeft(parent, parent.right);
				} else {
					// reached the root
					this.root = singleRotateLeft(parent, parent.right);
				}
				return;
			} else if (parent.balance == Code.LEFT) {
				parent.balance = shiftBalanceRight(parent.balance);
				return; // found a left weighted node, everything upwards can
						// not be affected
			} else {
				parent.balance = shiftBalanceRight(parent.balance);
			}
		}
	}

	/**
	 * 
	 * @param c
	 *            character to add
	 * @param pos
	 *            character added in this inorder position
	 * @throws IndexOutOfBoundsException
	 *             id pos is negative or too large for this tree
	 */
	public void add(char c, int pos) throws IndexOutOfBoundsException {
		if (pos < 0 || pos > this.size)
			throw new IndexOutOfBoundsException();
		if (pos == this.size) {
			this.add(c);
			return;
		}

		this.root = this.root.add(c, pos, this).node;
		this.size++;
	}

	/**
	 * 
	 * @param pos
	 *            position of character to delete from this tree
	 * @return the character that is deleted
	 * @throws IndexOutOfBoundsException
	 */
	public char delete(int pos) throws IndexOutOfBoundsException {
		if (pos < 0 || pos >= size) {
			throw new IndexOutOfBoundsException();
		}
		DeleteItem i = this.root.delete(pos, this);
		this.root = i.node;
		size--;
		return i.c;
	}

	/**
	 * 
	 * @param pos
	 *            position in the tree
	 * @return the character at that position
	 * @throws IndexOutOfBoundsException
	 */
	public char get(int pos) throws IndexOutOfBoundsException {
		return getNodeAt(pos).element;
	}

	private Node getNodeAt(int pos) {
		if (pos < 0 || pos >= this.size)
			throw new IndexOutOfBoundsException();

		Node currentNode = this.root;

		// this is supposing the rank field holds size of the left subtree
		while (currentNode != null && currentNode.rank != pos) {
			if (currentNode.rank > pos) {
				currentNode = currentNode.left;
			} else if (currentNode.rank < pos) {
				// if I decide to go right, update the rank I'm looking for
				// within the right subtree
				pos -= currentNode.rank + 1;
				currentNode = currentNode.right;
			}
		}

		return currentNode;
	}

	/**
	 * This method operates in O(length*log N), where N is the size of this tree.
	 * 
	 * @param pos
	 *            location of the beginning of the string to retrieve
	 * @param length
	 *            length of the string to retrieve
	 * @return string of length that starts in position pos
	 * @throws IndexOutOfBoundsException
	 *             unless both pos and pos+length-1 are legitimate indexes within this tree.
	 */
	public String get(int pos, int length) throws IndexOutOfBoundsException {
		if (pos < 0 || pos + length > this.size || length < 0)
			throw new IndexOutOfBoundsException();

		if (length == 0) {
			return "";
		}

		// This constructor is special
		// It was adapted to deepen in the tree in log n complexity to find the first node
		// Always picking only one of the children to deepen into
		// And builds up the essential(only) stack of elements necessary to find the successors
		// Avoiding any unrelated node in this stack
		InOrder itr = new InOrder(this, pos);

		StringBuilder s = new StringBuilder();
		for (; itr.isValid() && length > 0; itr.advance()) {
			s.append(itr.current.element);
			length--;
		}

		return s.toString();
	}

	/**
	 * This method is provided for you, and should not need to be changed. If split() and concatenate() are O(log N)
	 * operations as required, delete should also be O(log N)
	 * 
	 * @param start
	 *            position of beginning of string to delete
	 * 
	 * @param length
	 *            length of string to delete
	 * @return an EditTree containing the deleted string
	 * @throws IndexOutOfBoundsException
	 *             unless both start and start+length-1 are in range for this tree.
	 */
	public EditTree delete(int start, int length) throws IndexOutOfBoundsException {
		if (start < 0 || start + length >= this.size())
			throw new IndexOutOfBoundsException((start < 0) ? "negative first argument to delete"
					: "delete range extends past end of string");
		EditTree t2 = this.split(start);
		EditTree t3 = t2.split(length);
		this.concatenate(t3);

		return t2;
	}

	/**
	 * Append (in time proportional to the log of the size of the larger tree) the contents of the other tree to this
	 * one. Other should be made empty after this operation.
	 * 
	 * @param other
	 * @throws IllegalArgumentException
	 *             if this == other
	 */
	public void concatenate(EditTree other) throws IllegalArgumentException {
		if (this == other)
			throw new IllegalArgumentException();

		if (other.root != null && this.root != null) {
			if (other.height() <= this.height()) {

				Node q = other.root;

				while (q.left != null) {

					q = q.left;
				} // q equals first inorder element of other.
				other.delete(0); // delete q's old location

				concatenate(this, q, other);

			} else { // if (other.height() > this.height())

				Node q = this.root;

				while (q.right != null) {
					q = q.right;
				} // q equals last inorder element of this.
				this.delete(this.size - 1);

				concatenate(this, q, other);
			}
		}
		if (this.root == null && other.root != null) {
			this.root = other.root;
			this.size = other.size;
			other.root = null; // delete other
			other.size = 0;
		}

	}

	private EditTree concatenate(EditTree T, Node q, EditTree V) {

		if (V.height() <= T.height()) {

			Node p = T.root;
			Stack<Node> s = new Stack<Node>();
			Node parent = null;

			int cumulitiveRank = 0; // needed to find rank of q

			int height = -1;
			if (V.root != null)
				height = V.height(); // stops null pointer exception if
										// you delete V's root as q
			int Theight = T.height();
			while (Theight - height > 0) {

				s.push(p);
				if (p.balance == Code.LEFT) {
					Theight -= 2;
				} else {
					Theight--;
				}

				cumulitiveRank += p.rank + 1;
				parent = p;
				p = p.right; // go down right side of T

			}

			int rank = T.size - cumulitiveRank;
			T.size = T.size + V.size + 1; // set new size now (the
											// +1
											// is from q)
			q.right = V.root;
			q.left = p;
			q.rank = rank;
			// System.out.println(p.element);
			if (Theight == height) { // height() when called
										// on a
										// tree subtracts one
										// from
										// the node
										// version of height().
				q.balance = Code.SAME;
			} else if (Theight > height) {
				q.balance = Code.LEFT;
			} else {
				q.balance = Code.RIGHT;
			}
			if (parent != null) { // parent == null happens if the trees
									// initially have the same height
				s.peek().right = q;
			}

			if (parent == null) {
				T.root = q;
			}
			V.root = null;
			V.size = 0;
			// Below is rebalance code
			while (!s.isEmpty()) {
				Node a = s.pop();

				if (a.balance == Code.LEFT) {
					a.balance = Code.SAME;
					//break;
				} else if (a.balance == Code.SAME) {
					a.balance = Code.RIGHT;
				} else {
					Code c = a.right.balance;
					if (c == Code.RIGHT || c == Code.SAME) { // we need to do a
																// single
																// shift left
						Node b = T.singleRotateLeft(a, a.right);
						if (s.empty())
							T.root = b;
						else
							s.peek().right = b;
						if (c == Code.RIGHT){
							break;
					}

					} else { // we need to do a double shift left
						Node b = T.doubleRotateLeft(a, a.right.left, a.right);
						if (s.empty())
							T.root = b;
						else
							s.peek().right = b;
						break;
					}
				}
			}
		} else { // if (V.height() > T.height())

			Node p = V.root;
			Stack<Node> s = new Stack<Node>();
			Node parent = null;

			int height = -1;
			if (T.root != null)
				height = T.height(); // stops null pointer exception if
										// you delete T's root as q
			int pheight = V.height();
			while (pheight - height > 0) {
				s.push(p);

				if (p.balance == Code.RIGHT) {
					pheight -= 2;
				} else {
					pheight--;
				}
				
				parent = p;
				p = p.left;
			}
		

			int TSize = T.size;
			q.left = T.root;
			q.right = p;
			q.rank = TSize;

			if (pheight == height) { // height() when called
										// on a
										// tree subtracts one
										// from
										// the node
										// version of height().
				q.balance = Code.SAME;
			} else if (pheight > height) {
				q.balance = Code.RIGHT;
			} else {
				q.balance = Code.LEFT;
			}
			if (parent != null) { // parent == null happens if the trees
									// initially have the same height
				s.peek().left = q;
			}

			// Below is rebalance code
			T.root = V.root; // T.root needs to be at the of the
								// tree
			T.size = T.size + V.size + 1;
			V.root = null; // delete V
			V.size = 0;

			while (!s.isEmpty()) {
				Node a = s.pop();
				a.rank = a.rank + TSize + 1;
				if (a.balance == Code.RIGHT) {
					a.balance = Code.SAME;
				//	break;
				} else if (a.balance == Code.SAME) {
					a.balance = Code.LEFT;
				} else {
					Code c = a.left.balance;
					if (c == Code.LEFT || c == Code.SAME) { // we need to do a
						// single
						// shift right
						Node b = T.singleRotateRight(a, a.left);
						if (s.empty())
							T.root = b;
						else
							s.peek().left = b;
						if (c == Code.LEFT) {
							break;
						}
					} else { // we need to do a double shift right
						Node b = T.doubleRotateRight(a, a.left.right, a.left);
						if (s.empty())
							T.root = b;
						else
							s.peek().left = b;
						break;
					}
				}
			}
		}

		return T;
	}

	/**
	 * This operation must be done in time proportional to the height of this tree.
	 * 
	 * @param pos
	 *            where to split this tree
	 * @return a new tree containing all of the elements of this tree whose positions are >= position. Their nodes are
	 *         removed from this tree.
	 */
	public EditTree split(int pos) {
		if (pos < 0 || pos > this.size)
			throw new IndexOutOfBoundsException();

		if (pos == this.size) {
			return new EditTree();
		}

		int previousSize = this.size;
		int originalPos = pos;

		Stack<Node> pathStack = new Stack<Node>();
		Stack<Integer> partialSizeStack = new Stack<Integer>();

		Node currentNode = this.root;
		// this is supposing the rank field holds size of the left subtree

		partialSizeStack.push(previousSize);
		
		while (currentNode != null && currentNode.rank != pos) {
			if (currentNode.rank > pos) {
				partialSizeStack.push(currentNode.rank);
				pathStack.push(currentNode);
				currentNode = currentNode.left;
			} else if (currentNode.rank < pos) {
				partialSizeStack.push(partialSizeStack.peek() - (currentNode.rank + 1));
				// if I decide to go right, update the rank I'm looking for within the right subtree
				pos -= currentNode.rank + 1;
				pathStack.push(currentNode);
				currentNode = currentNode.right;
			}
		}
		if (currentNode == null) {
			throw new IndexOutOfBoundsException();
		}

		EditTree S = this, T = new EditTree();
		Node current, child;

		current = currentNode;

		S.root = current.left;
		S.size = current.rank;

		T.root = current.right;
		T.size = partialSizeStack.peek() - current.rank - 1;

		T.add(current.element, 0);

		while (!pathStack.isEmpty()) {
			child = current;
			current = pathStack.pop();
			partialSizeStack.pop();

			if (child == current.right) {
				EditTree currentLeft = new EditTree();
				currentLeft.root = current.left;
				currentLeft.size = current.rank;
				S = concatenate(currentLeft, current, S);
			} else {
				EditTree currentRight = new EditTree();
				currentRight.root = current.right;

				if (pathStack.isEmpty()) {
					currentRight.size = previousSize - current.rank - 1;
				} else {
					if (pathStack.peek().right != current) {
						currentRight.size = pathStack.peek().rank - current.rank - 1;
					} else {
						currentRight.size = partialSizeStack.peek() - current.rank - 1;
					}
				}

				T = concatenate(T, current, currentRight);
			}
		}

		T.size = previousSize - originalPos;
		S.size = originalPos;
		this.root = S.root;
		this.size = S.size;

		return T;
	}

	/**
	 * Don't worry if you can't do this one efficiently.
	 * 
	 * @param s
	 *            the string to look for
	 * @return the position in this tree of the first occurrence of s; -1 if s does not occur
	 */
	public int find(String s) {
		return find(s, 0);
	}

	/**
	 * 
	 * @param s
	 *            the string to search for
	 * @param pos
	 *            the position in the tree to begin the search
	 * @return the position in this tree of the first occurrence of s that does not occur before position pos; -1 if s
	 *         does not occur
	 */
	public int find(String s, int pos) {
		int length = s.length();

		if (length == 0) {
			return pos;
		}

		if (pos < 0 || pos > this.size)
			return -1;

		if (pos + length - 1 < 0 || pos + length - 1 > this.size)
			return -1;

		// This constructor is special
		// It was adapted to deepen in the tree in log n complexity to find the first node
		// Always picking only one of the children to deepen into
		// And builds up the essential(only) stack of elements necessary to find the successors
		// Avoiding any unrelated node in this stack
		InOrder itr = new InOrder(this, pos);

		boolean found = false;
		int matched = 0;
		while (pos <= this.size && itr.isValid()) {
			if (itr.current.element == s.charAt(matched)) {
				matched++;
			} else {
				matched = 0;
				if (pos + length > size) {
					break;
				}
			}

			if (matched == length) {
				found = true;
				break;
			}

			itr.advance();
			pos++;
		}

		if (found) {
			return pos - length + 1;
		}

		return -1;
	}

	/**
	 * @return The root of this tree.
	 */
	public Node getRoot() {
		return this.root;
	}

	/**
	 * Rotates the tree left at the given location. This supposes this method is called when both nodes are heavy on the
	 * right side. This also supposes the difference in the balance is 2.
	 * 
	 * @param unbalancedNode
	 *            - The unbalanced node
	 * @param rightChild
	 *            - The child in the unbalanced side (right)
	 * @return the node at the head of the subtree
	 */
	public Node singleRotateLeft(Node unbalancedNode, Node rightChild) {
		this.rotationCount++;

		unbalancedNode.right = rightChild.left;
		unbalancedNode.balance = rightChild.balance == Code.RIGHT ? Code.SAME : Code.RIGHT;
		rightChild.left = unbalancedNode;

		rightChild.balance = rightChild.balance == Code.RIGHT ? Code.SAME : Code.LEFT;

		rightChild.rank = rightChild.rank + unbalancedNode.rank + 1;
		return rightChild;
	}

	/**
	 * Rotates the tree right at the given location. This supposes this method is called when both nodes are heavy on
	 * the left side. This also supposes the difference in the balance is 2.
	 * 
	 * @param unbalancedNode
	 *            - The unbalanced node
	 * @param leftChild
	 *            - The child in the unbalanced side (left)
	 * @return the node at the head of the subtree
	 */
	public Node singleRotateRight(Node unbalancedNode, Node leftChild) {
		this.rotationCount++;

		unbalancedNode.left = leftChild.right;
		unbalancedNode.balance = leftChild.balance == Code.LEFT ? Code.SAME : Code.LEFT;

		leftChild.right = unbalancedNode;
		leftChild.balance = leftChild.balance == Code.LEFT ? Code.SAME : Code.RIGHT;

		unbalancedNode.rank = unbalancedNode.rank - leftChild.rank - 1;
		return leftChild;
	}

	/**
	 * Does a double left rotation at the given nodes
	 * 
	 * @param unbalancedNode
	 *            - The unbalanced node to the right
	 * @param leftGrandchild
	 *            - The Grandchild to the left of the heavy child
	 * @param rightChild
	 *            - The child on the heavy side (right)
	 * @return the head of the subtree
	 */
	public Node doubleRotateLeft(Node unbalancedNode, Node leftGrandchild, Node rightChild) {
		this.rotationCount += 2;

		unbalancedNode.right = leftGrandchild.left;
		if (leftGrandchild.balance == Code.RIGHT) {
			// the left side was smaller and was put in the right of the other
			// node
			// so the other node has a smaller right side
			// and thus is heavy on the left
			unbalancedNode.balance = Code.LEFT;
		} else {
			unbalancedNode.balance = Code.SAME;
		}

		rightChild.left = leftGrandchild.right;
		if (leftGrandchild.balance == Code.LEFT) {
			// the right side was smaller and was put in the left of the other
			// node
			// so the other node has a smaller left side
			// and thus is heavy on the right
			rightChild.balance = Code.RIGHT;
		} else {
			rightChild.balance = Code.SAME;
		}

		leftGrandchild.left = unbalancedNode;
		leftGrandchild.right = rightChild;
		leftGrandchild.balance = Code.SAME;

		rightChild.rank = rightChild.rank - leftGrandchild.rank - 1;
		leftGrandchild.rank = leftGrandchild.rank + 1 + unbalancedNode.rank;
		return leftGrandchild;
	}

	/**
	 * Does a double right rotation at the given nodes
	 * 
	 * @param unbalancedNode
	 *            - The unbalanced node to the left
	 * @param rightGrandchild
	 *            - The Grandchild to the right of the heavy child
	 * @param leftChild
	 *            - The child on the heavy side (left)
	 * @return the head of the subtree
	 */
	public Node doubleRotateRight(Node unbalancedNode, Node rightGrandchild, Node leftChild) {
		this.rotationCount += 2;

		unbalancedNode.left = rightGrandchild.right;
		if (rightGrandchild.balance == Code.LEFT) {
			// the right side was smaller and was put in the left of the other
			// node
			// so the other node has a smaller left side
			// and thus is heavy on the right
			unbalancedNode.balance = Code.RIGHT;
		} else {
			unbalancedNode.balance = Code.SAME;
		}

		leftChild.right = rightGrandchild.left;
		if (rightGrandchild.balance == Code.RIGHT) {
			// the left side was smaller and was put in the right of the other
			// node
			// so the other node has a smaller right side
			// and thus is heavy on the left
			leftChild.balance = Code.LEFT;
		} else {
			leftChild.balance = Code.SAME;
		}

		rightGrandchild.right = unbalancedNode;
		rightGrandchild.left = leftChild;
		rightGrandchild.balance = Code.SAME;

		rightGrandchild.rank = leftChild.rank + rightGrandchild.rank + 1;
		unbalancedNode.rank = unbalancedNode.rank - rightGrandchild.rank - 1;
		return rightGrandchild;
	}

	/**
	 * Returns the code that is shifted to the right
	 * 
	 * @param c
	 * @return code that is shifted to the right
	 */
	public static Code shiftBalanceRight(Code c) {
		if (c == Code.LEFT)
			return Code.SAME;
		if (c == Code.SAME)
			return Code.RIGHT;
		throw new UnsupportedOperationException();
	}

	/**
	 * Returns the code that is shifted to the left
	 * 
	 * @param c
	 * @return code that is shifted to the left
	 */
	public static Code shiftBalanceLeft(Code c) {
		if (c == Code.RIGHT)
			return Code.SAME;
		if (c == Code.SAME)
			return Code.LEFT;
		throw new UnsupportedOperationException();
	}

}
